package com.googlecode.kipler.common;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * This class generates subsets of a given set with specific cardinality. This
 * set can be any instance of {@link Set} such as a set of integers, Objects,
 * etc.
 * 
 * Special thanks goes to Önder Gürcan for his hint on using bit sets and Ahmet
 * Sıkıcı for actually developing the algorithm.
 * 
 * @author İnanç Seylan
 * 
 */
public class SubsetGenerator<E> implements Iterable<Set<E>> {
	/**
	 * The cardinality of the given set.
	 */
	private int setCardinality;

	/**
	 * The cardinality of the wanted subsets.
	 */
	private int subsetCardinality;

	/**
	 * 
	 */
	private int currItem;

	/**
	 * This class works on a bit set to generate all possible combinations. This
	 * field stores the current bit set.
	 */
	private BitSet bitSet;

	/**
	 * This list is used to map the current bit set into the elements of the
	 * given set.
	 */
	private List<E> elements;

	/**
	 * This field is true if we are generating the first combination.
	 */
	private boolean initial;

	/**
	 * This field is true if we want a n element subset of a n element set.
	 */
	private boolean setCardinalityEqualsSubsetCardinality;

	/**
	 * This field is for when the subset cardinality exceeds the set's
	 * cardinality which is an error.
	 */
	private boolean setCardinalityIsLessThanSubsetCardinality;

	/**
	 * This field is true if we want the 0 element subset of a set.
	 */
	private boolean emptySet;

	/**
	 * This field stores the locations of each item, i.e. indices of true values
	 * in the bitset. There must be exactly {@link #subsetCardinality} number of
	 * items.
	 */
	private int[] itemLocations;

	private class SubsetIterator implements Iterator<Set<E>> {
		/**
		 * 
		 * @return true if there are more subsets.
		 */
		public boolean hasNext() {
			boolean result;
			if (setCardinalityIsLessThanSubsetCardinality) {
				result = false;
			} else if (setCardinalityEqualsSubsetCardinality | emptySet) {
				result = true;
				setCardinalityEqualsSubsetCardinality = false;
				emptySet = false;
			} else {
				result = !isFinished();
			}
			return result;
		}

		/**
		 * 
		 * @return the next subset.
		 */
		public Set<E> next() {
			makeMove();
			return translate(bitSet);
		}

		public void remove() {
			// do nothing
		}

	}

	/**
	 * The default constructor
	 * 
	 * @param set
	 *            The given set.
	 * @param n
	 *            The cardinality of wanted subsets.
	 */
	public SubsetGenerator(Set<E> set, int n) {
		elements = new ArrayList<E>(set);
		setCardinality = set.size();
		subsetCardinality = n;
		currItem = n - 1;
		itemLocations = new int[n];
		for (int i = 0; i < n; i++) {
			itemLocations[i] = i;
		}
		initial = true;
		bitSet = initialPosition();
		setCardinalityEqualsSubsetCardinality = (setCardinality == subsetCardinality);
		setCardinalityIsLessThanSubsetCardinality = (setCardinality < subsetCardinality);
		emptySet = (n == 0);
	}

	/**
	 * The initial bit set begins with {@link #subsetCardinality} no of 1's.
	 * 
	 * @return the positions of items in the initial bit set.
	 */
	private BitSet initialPosition() {
		BitSet result = new BitSet(setCardinality);
		for (int i = 0; i < subsetCardinality; i++) {
			result.set(i, true);
		}
		return result;
	}

	/**
	 * 
	 * @return true if no more subsets can be generated.
	 */
	private boolean isFinished() {
		boolean result = true;
		for (int i = setCardinality - subsetCardinality; i < setCardinality; i++) {
			if (!bitSet.get(i)) {
				result = false;
				break;
			}
		}
		return result;
	}

	/**
	 * Makes the next move, i.e. generate the next bit set.
	 */
	private void makeMove() {
		// nothing to do if it's the initial bit set
		if (initial) {
			initial = false;
		} // move the current item, i.e. the rightmost true bit to right.
		else if (itemLocations[currItem] < setCardinality - 1) {
			bitSet.set(itemLocations[currItem], false);
			itemLocations[currItem]++;
			bitSet.set(itemLocations[currItem], true);
		} // if the rightmost n true bits are at the rightmost positions, then
		// move their predecessor true bit one step to the right while ordering
		// the rightmost n bits in consecutive positions.
		else {
			// select the predecessor
			while (itemLocations[currItem] == setCardinality - 1
					|| bitSet.get(itemLocations[currItem] + 1)) {
				currItem--;
			}
			// arrange the new position of the predecessor
			bitSet.set(itemLocations[currItem], false);
			itemLocations[currItem]++;
			bitSet.set(itemLocations[currItem], true);
			// sequence the n rightmost bits consecutively
			int followingOneCount = subsetCardinality - currItem - 1;
			for (int i = itemLocations[currItem] + 1, j = 1; i < setCardinality; i++, j++) {
				if (followingOneCount > 0) {
					bitSet.set(i, true);
					itemLocations[currItem + j] = i;
					followingOneCount--;
				} else {
					bitSet.set(i, false);
				}
			}
			// move the selected item to the rightmost available bit
			while (itemLocations[currItem] < setCardinality - 1
					&& bitSet.get(itemLocations[currItem] + 1)) {
				currItem++;
			}
		}
	}

	/**
	 * This method translates the given bit set into a subset of the original
	 * set. It uses the true bits in the given bit set to identify the elements
	 * of the subset.
	 * 
	 * @param bitSet
	 *            The bit set to be translated.
	 * @return a subset of the original set.
	 */
	private Set<E> translate(BitSet bitSet) {
		Set<E> result = new HashSet<E>();
		for (int i = 0; i < bitSet.size(); i++) {
			if (bitSet.get(i)) {
				result.add(elements.get(i));
			}
		}
		return result;
	}

	public Iterator<Set<E>> iterator() {
		return new SubsetIterator();
	}
}
